package Leetcode第一期;

import java.util.HashMap;
import java.util.Map;

//无重复字符的最长子串
public class 无重复字符的最长子串_3 {

    public int lengthOfLongestSubstring(String s) {
        /*int n=s.length();
        Set set=new HashSet();
        int i=0,j=0,ans=0;

        while (i<n && j<n){
            if(!set.contains(s.charAt(j))){
                set.add(s.charAt(j++));
                ans=Math.max(ans,j-i);
            }else{
                set.remove(s.charAt(i++));
            }
        }
        return ans;*/

        int n = s.length(), ans = 0;
        Map<Character, Integer> map = new HashMap<>(); // current index of character
        // try to extend the range [i, j]
        for (int j = 0, i = 0; j < n; j++) {
            if (map.containsKey(s.charAt(j))) {
                i = Math.max(map.get(s.charAt(j)), i);
            }
            ans = Math.max(ans, j - i + 1);
            //放入当前检测位的字符和位置
            map.put(s.charAt(j), j + 1);
        }
        return ans;
    }
}
